//
// Created by cyber on 2021/8/24.
//
#include <algorithm>
#include <iostream>
#include <memory>
/*
 * _________________________________________________________________
 * |  0  |  1  |  2  |  3  |  4  |          未构造的元素              |
 * -----------------------------------------------------------------
 * ↑                              ↑                                 ↑
 * elements                       first_free                        cap
 *
 */
using namespace std;
class StrVec
{
    friend bool operator==(const StrVec & lhs, const StrVec & rhs);
    friend bool operator!=(const StrVec & lhs, const StrVec & rhs);
    friend bool operator<(const StrVec & lhs, const StrVec & rhs);
    friend bool operator>(const StrVec & lhs, const StrVec & rhs);
    friend bool operator<=(const StrVec & lhs, const StrVec & rhs);
    friend bool operator>=(const StrVec & lhs, const StrVec & rhs);
public:
    StrVec()
        : elements(nullptr)
        , first_free(nullptr)
        , cap(nullptr)
    {}
    StrVec(initializer_list<std::string> init_list);
    virtual ~StrVec();

    //拷贝构造函数
    StrVec(const StrVec &);
    //拷贝赋值运算符
    StrVec & operator=(const StrVec &);
    StrVec & operator=(initializer_list<std::string> il);
    //移动构造
    StrVec(StrVec &&) noexcept;
    //移动赋值

    std::string &       operator[](std::size_t n) { return elements[n]; }
    const std::string & operator[](std::size_t n) const { return elements[n]; }

    void push_back(const std::string &);//拷贝元素
    void push_back(std::string &&);

    size_t size() const { return first_free - elements; }
    size_t capacity() const { return cap - elements; }

    std::string * begin() const { return elements; }
    std::string * end() const { return first_free; }

    void reserve (size_t n){ if (n > capacity()) reallocate(n); }
private:
    void chk_n_alloc()
    {
        if(size() == capacity())
            reallocate();
    }
    void free();
    void reallocate();
    void reallocate(size_t new_capacity);
    void resize(size_t n);
    void resize(size_t n,const std::string &s);
    std::pair<std::string *, std::string *> alloc_n_copy(const std::string *, const std::string *);

private:
    static std::allocator<std::string> alloc;

    std::string * elements;
    std::string * first_free;
    std::string * cap;
};
StrVec::~StrVec()
{
    free();
}
StrVec::StrVec(const StrVec & s)
{
    /**
     * alloc_n_copy 的返回值是一个指针的pair。其 first成员指向第一个构造的元素，second 成员指向最后一个构造的元素之后的位置。由于alloc_n_copy分配的空间恰好容纳给定的元素，cap也指向最后一个构造的元素之后的位置。
     */
    //调用alloc_n_copy分配空间以容纳与s中一样多的元素
    auto new_data = alloc_n_copy(s.begin(), s.end());
    elements      = new_data.first;

    first_free = cap = new_data.second;
}
StrVec & StrVec::operator=(const StrVec & rhs)
{
    //调用alloc_n_copy 分配内存，大小与rhs中元素占用空间一样多
    auto data = alloc_n_copy(rhs.begin(), rhs.end());
    free();
    elements   = data.first;
    first_free = cap = data.second;
    return *this;
}
void StrVec::push_back(const string & s)
{
    chk_n_alloc();//确保有空间容纳新元素

    // 在first_free指向的元素中构造s的副本
    alloc.construct(first_free++, s);
}
void StrVec::push_back(std::string && s)
{
    chk_n_alloc();//如果需要的话为StrVec重新分配内存
    alloc.construct(first_free++, std::move(s));
}
void StrVec::free()
{
    //不能传递给deallocate一个空指针，如果elements为nullptr，函数什么也不做
     if (nullptr != elements) {
         //方法一
         //逆序销毁旧元素
//         for(auto p = first_free; p != elements; /*空*/)
//             alloc.destroy(--p);
//         方法2
         for_each(elements, first_free, [](std::string & s) { alloc.destroy(&s); });

         alloc.deallocate(elements, cap - elements);
     }

}
//construct 构造版本
void StrVec::reallocate()
{
    //我们将分配当前大小两倍的内存空间
    auto new_capacity = size() ? 2 * size() : 1;

    //分配新内存
    auto new_data     = alloc.allocate(new_capacity);

    //将数据从旧内存移动到新内存
    auto dest         = new_data;//指向新数组中下一个空闲位置
    auto elem         = elements;//指向旧数组中下一个元素

    for(size_t i = 0; i != size(); ++i)
        alloc.construct(dest++, std::move(*elem++));

    free();//一旦我们移动完元素就释放旧内存空间

    //更新我们的数据结构，执行新元素
    elements   = new_data;
    first_free = dest;
    cap        = elements + new_capacity;
}

//uninitialized_copy 版本
//void StrVec::reallocate()
//{
//    //我们将分配当前大小两倍的内存空间
//    auto new_capacity = size() ? 2 * size() : 1;
//
//    auto first        = alloc.allocate(new_capacity);
//    auto last         = uninitialized_copy(make_move_iterator(begin()), make_move_iterator(end()), first);
//
//    free();//一旦我们移动完元素就释放旧内存空间
//
//    //更新我们的数据结构，执行新元素
//    elements   = first;
//    first_free = last;
//    cap        = elements + new_capacity;
//}

std::pair<std::string *, std::string *> StrVec::alloc_n_copy(const std::string * b, const std::string * e)
{
    //分配空间保存给定范围中的元素
    auto data = alloc.allocate(e - b);
    //初始化并返回一个pair，该pair由data和uninitialized_copy的返回值构成
    return {data, uninitialized_copy(b, e, data)};
}
void StrVec::reallocate(size_t new_capacity)
{                                               //分配新内存
    auto newdata = alloc.allocate(new_capacity);//将数据从旧空间移动到新空间
    auto dest    = newdata;                     //dest指向新空间中第一个空闲位置
    auto elem    = elements;                    //指向旧空间中下一个元素

    for(size_t i = 0; i != size(); ++i)
        alloc.construct(dest++, std::move(*elem++));
    free();//数据移动完毕，释放旧空间

    //更新指针，指向新空间开始、末尾位置及第一个空闲位置
    elements   = newdata;
    first_free = dest;
    cap        = elements + new_capacity;
}
void StrVec::resize(size_t n)
{
    //添加空字符串
    if(n > size()) {
        while(size() < n)
            push_back("");
    }
    //销毁字符串
    else if(n < size()) {
        while(size() > n)
            alloc.destroy(--first_free);
    }
}
void StrVec::resize(size_t n, const string & s)
{
    //添加空字符串
    if(n > size()) {
        while(size() < n)
            push_back(s);
    }
}
StrVec::StrVec(initializer_list<std::string> il)
{
    //调用alloc_n_copy分配与列表il中元素数目一样多的空间
    auto newdata = alloc_n_copy(il.begin(), il.end());
    elements     = newdata.first;
    first_free = cap = newdata.second;
}
StrVec::StrVec(StrVec && rhs) noexcept
    : elements(rhs.elements)
    , first_free(rhs.first_free)
    , cap(rhs.cap)
{
    rhs.elements = rhs.first_free = rhs.cap = nullptr;
}
bool operator==(const StrVec & lhs, const StrVec & rhs)
{
    if(lhs.size() != rhs.size())
        return false;

    for(auto itr1 = lhs.begin(), itr2 = rhs.begin(); itr1 != lhs.end() && itr2 != rhs.end(); itr1++, itr2++)
        if(*itr1 != *itr2)
            return false;
    return true;
}
bool operator!=(const StrVec & lhs, const StrVec & rhs)
{
    return !(rhs == lhs);
}
bool operator<(const StrVec & lhs, const StrVec & rhs)
{
    for(auto p1 = lhs.begin(), p2 = rhs.begin(); p1 != lhs.end() && p2 != rhs.end(); p1++, p2++) {
        if(*p1 < *p2)
            //之前的string都相等，当前string更小
            return true;
        else if(*p1 > *p2)
            //之前的string 都相等，当前string更大
            return false;
        // s1中的所有string都与s2中的string相等，且更短
        if(p1 == lhs.end() && p2 != rhs.end())
            return true;
        return false;
    }
}
bool operator>(const StrVec & lhs, const StrVec & rhs)
{
    for(auto p1 = lhs.begin(), p2 = rhs.begin(); p1 != lhs.end() && p2 != rhs.end(); p1++, p2++) {
        if(*p1 < *p2)
            //之前的string都相等，当前string更小
            return true;
        else if(*p1 > *p2)
            //之前的string 都相等，当前string更大
            return false;
        // s1中的所有string都与s2中的string相等，且更短
        if(p1 != lhs.end() && p2 == rhs.end())
            return true;
        return false;
    }
}
bool operator<=(const StrVec & lhs, const StrVec & rhs)
{
    for(auto p1 = lhs.begin(), p2 = rhs.begin(); p1 != lhs.end() && p2 != rhs.end(); p1++, p2++) {
        if(*p1 < *p2)
            //之前的string都相等，当前string更小
            return true;
        else if(*p1 > *p2)
            //之前的string 都相等，当前string更大
            return false;
        // s1中的所有string都与s2中的string相等，且更短
        if(p1 == lhs.end())
            return true;
        return false;
    }
}
bool operator>=(const StrVec & lhs, const StrVec & rhs)
{
    for(auto p1 = lhs.begin(), p2 = rhs.begin(); p1 != lhs.end() && p2 != rhs.end(); p1++, p2++) {
        if(*p1 < *p2)
            //之前的string都相等，当前string更小
            return true;
        else if(*p1 > *p2)
            //之前的string 都相等，当前string更大
            return false;
        // s1中的所有string都与s2中的string相等，且更短
        if(p2 == rhs.end())
            return true;
        return false;
    }
}
StrVec & StrVec::operator=(initializer_list<std::string> il)
{
    auto data = alloc_n_copy(il.begin(), il.end());
    free();
    elements   = data.first;
    first_free = cap = data.second;
    return *this;
}
